package 中等.其他;

import java.util.HashMap;
import java.util.Map;

/**
 * 如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
 * 给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，
 * 然后得到一些单字符重复的子串。返回其中最长的子串的长度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/swap-for-longest-repeated-character-substring
 */
public class 单字符重复子串的最大长度_1156 {

    public static void main(String[] args) {

        System.out.println(maxRepOpt2("bbababaaaa"));

    }

    /**
     * 使用前缀和计算出
     * prefixSum[i] 表示包含 i 和之前连续的位置都是字符 text.CharAt(i) 的个数
     * suffixSum[i] 表示包含 i 和之后连续的位置都是字符 text.CharAt(i) 的个数
     * 遍历text，遍历到 i 时，j < i，尝试将 i 和 j 交换，取最长的子串长度
     */
    public static int maxRepOpt1(String text) {
        int ans = 1;
        char[] chars = text.toCharArray();
        int[] prefixSum = new int[text.length()];
        int[] suffixSum = new int[text.length()];
        prefixSum[0] = 1;
        suffixSum[text.length() - 1] = 1;
        for (int i = text.length() - 2; i >= 0; i--) {
            suffixSum[i] = 1;
            if (chars[i] == chars[i + 1]) {
                suffixSum[i] += suffixSum[i + 1];
            }
        }

        for (int i = 1; i < chars.length; i++) {
            prefixSum[i] = 1;
            if (chars[i] == chars[i - 1]) {
                prefixSum[i] += prefixSum[i - 1];
            }
            ans = Math.max(ans, prefixSum[i]);
            int afterCnt = 0;
            for (int j = i - 1; j >= 0; j--) {

                int curLen = 1;
                if (j <= (i - 1) - prefixSum[i - 1] && chars[j] == chars[i - 1]) {
                    curLen += Math.min(prefixSum[i - 1], i - 1 - j + 1);
                }
                if ((i + 1) < text.length() && chars[j] == chars[i + 1]) {
                    curLen += suffixSum[i + 1];
                }
                ans = Math.max(ans, curLen);


                if (j - 1 >= 0 && chars[j - 1] == chars[i]) {
                    ans = Math.max(ans, prefixSum[j - 1] + 1 + afterCnt);
                }

                if (chars[j] == chars[i]) {
                    afterCnt++;
                } else {
                    afterCnt = 0;
                }
            }
        }

        return ans;
    }

    /**
     * 滑动窗口
     * 窗口内允许存在两个不同的字符，如果窗口外面还有和
     * 窗口中较多字符的字符，那么窗口长度符合条件
     */
    public static int maxRepOpt2(String text) {
        int ans = 1;
        char[] chars = text.toCharArray();
        int[] record = new int[26];
        int pre = 0;
        for (int i = 0; i < chars.length; i++) {
            record[chars[i] - 'a']++;

            if (i >= 1 && chars[i] == chars[i - 1]) {
                ans = Math.max(ans, pre + 1);
                pre++;
            } else {
                pre = 1;
            }
        }
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        while (right < chars.length) {
            while (right < chars.length &&
                    (map.size() <= 1 || map.size() == 2 &&
                            map.containsKey(chars[right]))) {
                boolean flag = false;
                if (map.size() == 2) {
                    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                        if (entry.getValue() > 1 && entry.getKey() != chars[right]) {
                            flag = true;
                            break;
                        }
                    }
                }
                if (flag) break;

                map.put(chars[right], map.getOrDefault(chars[right], 0) + 1);
                right++;
            }

            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 1) {
                    if (record[entry.getKey() - 'a'] >= 2) ans = Math.max(ans, 2);
                } else {
                    if ((record[entry.getKey() - 'a'] - entry.getValue() >= 1)) {
                        ans = Math.max(ans, entry.getValue() + 1);
                    } else {
                        ans = Math.max(ans, entry.getValue());
                    }
                }
            }

            map.put(chars[left], map.get(chars[left]) - 1);
            if (map.get(chars[left]) == 0) {
                map.remove(chars[left]);
            }
            left++;
        }
        return ans;
    }

}
